//给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
//
// 示例 1：
//
// 输入: "babad"
//输出: "bab"
//注意: "aba" 也是一个有效答案。
//
//
// 示例 2：
//
// 输入: "cbbd"
//输出: "bb"
//
// Related Topics 字符串 动态规划


class Solution {
    public static String longestPalindrome(String s) {
        if (s.length() == 0) {
            return "";
        }
        int len = s.length();
        boolean flag[][] = new boolean[len][len];
        int start = 0;
        int maxlen = 1;
        for (int i = 0; i < len; i++) {
            for (int j = 0; j <= i; j++) {
                if (i - j < 2) {
                    flag[j][i] = s.charAt(i) == s.charAt(j);
                } else {
                    flag[j][i] = flag[j + 1][i - 1] && s.charAt(i) == s.charAt(j);
                }
                if (flag[j][i] && i - j + 1 > maxlen) {
                    start = j;
                    maxlen = i - j + 1;
                }
            }
        }
        return s.substring(start, start + maxlen);
    }

    public static void main(String[] args) {
        String str = "abcda";
        System.out.println(longestPalindrome(str));
    }
}
